package com.leetcode.algorithm.y22.m06;

/**
 * 72. 编辑距离
 * 
 * https://leetcode.cn/problems/edit-distance/
 * 
 * @author jie.deng
 *
 */
class Question0072Solution01 {

	public int minDistance(String word1, String word2) {
		// DP状态定义:
		// dp[i][j]表示 将 word1前i个字符 转换成 words2前j个字符 所使用的最少操作数
		int len1 = word1.length();
		int len2 = word2.length();
		int[][] dp = new int[len1 + 1][len2 + 1];
		dp[0][0] = 0;
		for (int i = 1; i <= len1; i++) {
			// word2为空，word1到word2的编辑距离是word1的长度
			dp[i][0] = i;
		}
		for (int i = 1; i <= len2; i++) {
			// word1为空，word1到word2的编辑距离是word2的长度
			dp[0][i] = i;
		}

		// 决策:a.插入一个字符 b.删除一个字符 c.替换一个字符 d.不需要编辑
		// 状态转移方程
		for (int i = 1; i <= len1; i++) {
			for (int j = 1; j <= len2; j++) {
				if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
					// d.不需要编辑
					dp[i][j] = dp[i - 1][j - 1];
				} else {
					dp[i][j] = Integer.MAX_VALUE;
					// c.替换一个字符
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
					// b.删除一个字符
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
					// a.插入一个字符
					dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
				}
			}
		}

		return dp[len1][len2];
	}

}